import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 刘柄华
 * Date: 2022-06-14
 * Time: 20:12
 */
public class Test04 {
    /*
     *    二叉树中和为某一值的路径(二)
     *    输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
     *     思路: 回溯
     * */

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        // 结果集
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        // 待选结果
        ArrayList<Integer> list = new ArrayList<>();
        if (root == null) return result;

        FindPathDFS(root, expectNumber, result, list);
        return result;
    }

    private void FindPathDFS(TreeNode root, int expectNumber, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        expectNumber -= root.val;
        if (root.left == null && root.right == null && expectNumber == 0) {
            // 注意 传入的 list (深浅拷贝)
            result.add(new ArrayList<>(list));
        }
        FindPathDFS(root.left, expectNumber, result, list);
        FindPathDFS(root.right, expectNumber, result, list);

        list.remove(list.size() - 1);
    }
}
